/**
 * //Given an m x n matrix, return all elements of the matrix in spiral order.
 * //
 * //
 * // Example 1:
 * //
 * //
 * //Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
 * //Output: [1,2,3,6,9,8,7,4,5]
 * //
 * //
 * // Example 2:
 * //
 * //
 * //Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
 * //Output: [1,2,3,4,8,12,11,10,9,5,6,7]
 * //
 * //
 * //
 * // Constraints:
 * //
 * //
 * // m == matrix.length
 * // n == matrix[i].length
 * // 1 <= m, n <= 10
 * // -100 <= matrix[i][j] <= 100
 * //
 * //
 * // Related Topics 数组 矩阵 模拟 👍 1228 👎 0
 */

package com.xixi.medium;

import java.util.ArrayList;
import java.util.List;

public class ID00054SpiralMatrix {
    public static void main(String[] args) {
        Solution solution = new ID00054SpiralMatrix().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        boolean[][] path;
        List<Integer> res;

        public List<Integer> spiralOrder(int[][] matrix) {

            int m = matrix.length;
            int n = matrix[0].length;
            res = new ArrayList<>(m * n);
            path = new boolean[m][n];
            moveRight(0, 0, m, n, matrix);
            return res;
        }

        public void moveRight(int startRow, int startCol, int m, int n, int[][] matrix) {
            int i = startCol;
            while (i < n && !path[startRow][i]) {
                res.add(matrix[startRow][i]);
                path[startRow][i] = true;
                i++;
            }
            //path[startRow][i] == true说明到头了，i-1是转折点，该往下走了,
            // matrix[startRow][i-1]已经在list中了，所以不能包含了，只能往下走,起始点就是matrix[startRow+1][i-1]
            if (startRow + 1 < m && !path[startRow + 1][i - 1]) {
                moveDown(startRow + 1, i - 1, m, n, matrix);
            }


        }

        public void moveDown(int startRow, int startCol, int m, int n, int[][] matrix) {
            int i = startRow;
            while (i < m && !path[i][startCol]) {
                res.add(matrix[i][startCol]);
                path[i][startCol] = true;
                i++;
            }
            //path[i][startCol] == true说明到头了，i-1是转折点，该往左走了,
            // matrix[i-1][startCol]已经在list中了，所以不能包含了，只能往左走,起始点就是matrix[i-1][startCol-1]
            if (startCol - 1 >= 0 && !path[i - 1][startCol - 1]) {
                moveLeft(i - 1, startCol - 1, m, n, matrix);
            }
        }

        public void moveLeft(int startRow, int startCol, int m, int n, int[][] matrix) {
            int i = startCol;
            while (i >= 0 && !path[startRow][i]) {
                res.add(matrix[startRow][i]);
                path[startRow][i] = true;
                i--;
            }
            //path[i][startCol] == true说明到头了，i-1是转折点，该往左走了,
            // matrix[i-1][startCol]已经在list中了，所以不能包含了，只能往左走,起始点就是matrix[i-1][startCol-1]
            if (startRow - 1 >= 0 && !path[startRow - 1][i + 1]) {
                moveUp(startRow - 1, i + 1, m, n, matrix);
            }
        }

        public void moveUp(int startRow, int startCol, int m, int n, int[][] matrix) {
            int i = startRow;
            while (i >= 0 && !path[i][startCol]) {
                res.add(matrix[i][startCol]);
                path[i][startCol] = true;
                i--;
            }
            //path[i][startCol] == true说明到头了，i-1是转折点，该往左走了,
            // matrix[i-1][startCol]已经在list中了，所以不能包含了，只能往左走,起始点就是matrix[i-1][startCol-1]
            if (startCol + 1 < n && !path[i + 1][startCol + 1]) {
                moveRight(i + 1, startCol + 1, m, n, matrix);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}